package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/30 11:28
 **/
public class Day45_3_Offer10_Fib {
    class Solution {
        public int fib(int n) {
            if(n < 2) return n;
            int[] dp = new int[n+1];
            dp[0] = 0; dp[1] = 1;
            for(int i = 2; i <= n; ++i){
                dp[i] = (dp[i-1] + dp[i-2])% 1000000007;
            }
            return dp[n];
        }
    }
}